package main

func dp(s string) [][]bool {
	m := make([][]bool, len(s))
	for i := range s {
		m[i] = make([]bool, len(s))
	}
	for i := len(s) - 1; i >= 0; i-- {
		for j := range s {
			if i >= j {
				m[i][j] = true
			} else {
				m[i][j] = m[i+1][j-1] && s[i] == s[j]
			}
		}
	}

	return m
}

func checkPartitioning(s string) bool {
    m := dp(s)
	for i := range s {
		if i == 0 {
			continue
		}
		for j := i + 1; j < len(s); j++ {
			if m[0][i-1] && m[i][j-1] && m[j][len(s)-1] {
				return true
			} 
		}
	}
	return false
}

func main() {
	println(checkPartitioning("bbab"))
}